/**
 * 139. 单词拆分
 * https://leetcode-cn.com/problems/word-break/
 */

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
function wordBreak(s, wordDict) {
  const wordsSet = new Set(wordDict);
  const lengthSet = new Set(wordDict.map((word) => word.length));
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i += 1) {
    for (let j = i; j >= 1; j -= 1) {
      if (
        lengthSet.has(i - j + 1)
        && wordsSet.has(s.substring(j - 1, i))
        && dp[j - 1]
      ) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

console.log(wordBreak('leetcode', ['leet', 'code']) === true);
console.log(wordBreak('applepenapple', ['apple', 'pen']) === true);
console.log(wordBreak('catsandog', ['cats', 'dog', 'sand', 'and', 'cat']) === false);
